#!/usr/bin/env python3
#coding:utf-8

import timeit

def bubble_sort(a):
    n = len(a)
    while n > 0:
        for i in range(n - 1):
            if a[i] > a[i+1]:
                a[i], a[i+1] = a[i+1], a[i]
        n -= 1  
def select_sort(a):
    for i in range(len(a)):
        for j in range(i, len(a)):
            if a[i] > a[j]:
                a[i], a[j] = a[j], a[i]

def insert_sort(a):
    for i in range(1, len(a)):
        v = a[i]
        for j in range(i-1, -1, -1):
            if v < a[j]:
                a[j+1] = a[j]
            else:
                a[j+1] = v
                break
def shell_sort(a, step):
    '''TODO:'''
    pass

def quick_sort(a, left, right):
    if (left >= right):
        return
    m = (right + left) // 2
    a[left], a[m] = a[m], a[left]
    pos = left
    for i in range(left + 1, right):
        if a[i] < a[left]:
            pos += 1
            a[i], a[pos] = a[pos], a[i]
    #print("left=", left, "right=", right, "pos", pos)        
    a[left], a[pos] = a[pos], a[left]
    quick_sort(a, left, pos - 1)
    quick_sort(a, pos + 1, right)

def merge_sort(a):
    def merge(l, r):
        i, j = 0, 0
        a = []
        while i < len(l) and j < len(r):
            if l[i] < r[j]:
                a.append(l[i])
                i += 1
            else:
                a.append(r[j])
                j += 1
        if i < len(l):
            a += l[i:len(l)]
        if j < len(r):
            a += r[j:len(r)]
        return a
    def merge_sort_(a, l, r):
        if l + 1 >= r:
            return a[l:r]
        al = merge_sort_(a, l, (l+r)//2)
        ar = merge_sort_(a, (l+r)//2, r)
        return merge(al, ar)
    return merge_sort_(a, 0, len(a))

def merge_sort1(a):
    def merge(a, b, l, r):
        m = (l+r)//2
        i, j, k = l, m, l
        while i < m and j < r:
            if a[i] < a[j]:
                b[k] = a[i]
                i += 1
            else:
                b[k] = a[j]
                j += 1
            k += 1
        if i < m:
            b[k:r] = a[i:m]
        if j < r:
            b[k:r] = a[j:r]
        a[l:r] = b[l:r]
    def merge_sort_(a, b, l, r):
        if l + 1 >= r:
            b[l] = a[l]
            return
        merge_sort_(a, b, l, (l+r)//2)
        merge_sort_(a, b, (l+r)//2, r)
        merge(a, b, l, r)    
    b = [0] * len(a)
    merge_sort_(a, b, 0, len(a))
    return b

def heap_sort(a):
    def adjust_heap(a, al, l):
        tmp = a[l]
        while True:
            i = 2*l+1
            if i >= al:
                break
            if i + 1 < al and a[i] < a[i+1]:
                i = i + 1
            if tmp < a[i] :
                a[l] = a[i]
                l = i
            else:
                break
        a[l] = tmp
            
    for i in range(len(a)//2-1, -1, -1):
        adjust_heap(a, len(a), i)
    for i in range(len(a)-1, -1, -1):
        a[0], a[i] = a[i], a[0]
        adjust_heap(a, i, 0)
    

def binnary_search(v, a, left, right):
    if left >= right:
        return False
    mid = (right + left) // 2
    if v < a[mid]:
        return binnary_search(v, a, left, mid - 1)
    elif v > a[mid]:
        return binnary_search(v, a, mid + 1, right)
    else:
        return True
    return False


def Test(t, num):
    sum = 0
    for i in range(num):
        sum += t.timeit(1)
    return sum/num

if __name__ == '__main__':
    import random
    NUM = 10
    t = timeit.Timer('sort.bubble_sort(a);', 'import sort; import random; a = [int(10000*random.random()) for x in range(2000)]')
    print ('bubble_sort: ', Test(t, NUM))
    a = [10, 67, 89, 278, 10, 20, 38, 28, 18, 8, 29]
    print('src:', a)
    bubble_sort(a)
    print('after bubble_sort', a)
    if binnary_search(18, a, 0, len(a)):
        print('binnary search 18: true')
    else:
        print('binnary search 18: false')
    
    if binnary_search(7, a, 0, len(a)):
        print('binnary search 7: true')
    else:
        print('binnary search 7: false')
    
    t = timeit.Timer('sort.quick_sort(a, 0, len(a))', 'import sort; import random; a = [int(10000*random.random()) for x in range(2000)]')
    print ('quick_sort: ', Test(t, NUM))
    a = [x*int(100*random.random()) for x in range(10)]
    print('src:', a)
    quick_sort(a, 0, len(a))
    print('after quick_sort', a)
    
    t = timeit.Timer('sort.merge_sort(a)', 'import sort; import random; a = [int(10000*random.random()) for x in range(2000)]')
    print ('merge_sort: ', Test(t, NUM))
    a = [x*int(100*random.random()) for x in range(10)]
    print('src:', a)
    a = merge_sort(a)
    print('after merge_sort', a)
    
    t = timeit.Timer('sort.merge_sort1(a)', 'import sort; import random; a = [int(10000*random.random()) for x in range(2000)]')
    print ('merge_sort1: ', Test(t, NUM))
    a = [x*int(100*random.random()) for x in range(10)]
    print('src:', a)
    a = merge_sort1(a)
    print('after merge_sort1', a)
    
    
    t = timeit.Timer('sort.select_sort(a);', 'import sort; import random; a = [int(10000*random.random()) for x in range(2000)];')
    print ('select_sort: ', Test(t, NUM))
    a = [x*int(100*random.random()) for x in range(10)]
    print('src:', a)
    select_sort(a)
    print('after select_sort', a)
    t = timeit.Timer('sort.insert_sort(a);', 'import sort; import random; a = [int(10000*random.random()) for x in range(2000)];')
    print ('insert_sort: ', Test(t, NUM))
    a = [x*int(100*random.random()) for x in range(10)]
    print('src:', a)
    insert_sort(a)
    print('after insert_sort', a)

    t = timeit.Timer('sort.heap_sort(a);', 'import sort; import random; a = [int(10000*random.random()) for x in range(2000)];')
    print ('heap_sort: ', Test(t, NUM))
    a = [x*int(100*random.random()) for x in range(10)]
    #a = [0, 70, 106, 48, 224, 375, 552, 273, 24, 837]
    print('src:', a)
    heap_sort(a)
    print('after heap_sort', a)
